// my_predictor.h - Daan Raman
// Meta predictor - this predictor consists of two meta predictors, metapredictor 1 is responsible
// for choosing between a second meta predictor and another predictor. This predictor represents the initial predictor we discussed in the project proposal.

// First meta predictor is guided using a tournament strategy

#include <iostream>
#include <string>
#include <cstdlib>
#include <stdio.h>
#include <stdlib.h>
#include <cstdlib>

using namespace std;

class my_update : public branch_update{
public:
	unsigned int address;
	unsigned int gshare_index;
	
	bool final_prediction;
	
	bool bimodal_prediction;
	bool gshare_prediction;
	bool second_prediction;	
	
};

class my_predictor : public branch_predictor{
public:
	
	//Part A - bimodal
	#define BIMODAL_INDEX_BITS 13
	unsigned int	bimodal_counters[1<< BIMODAL_INDEX_BITS];
	unsigned int	bimodal_index;	
	unsigned int	bimodal_history;	//Not used in decision, only to keep track of performance
	
	//PART B - gShare
	#define GSHARE_HISTORY_LENGTH 10
	#define GSHARE_TABLE_BITS 19
	unsigned int	gshare_history;
	unsigned char	gshare_counters[1 << GSHARE_TABLE_BITS];
	
	//PART C - two_level adaptive branch predictor
	unsigned int	two_level_history;
	unsigned int	two_level_counters[1<< 26];
	unsigned int	two_level_index;
	int gIndex;
	
	#define TWO_LEVEL_HISTORY_LENGTH	10
	#define TWO_LEVEL_INDEX_BITS (26 - TWO_LEVEL_HISTORY_LENGTH)
	
	//PART D - GENERAL USE
	
	//Shared	
	my_update u;
	branch_info bi;
	
	int tournament_choice;
	bool firstMeta;
	
	#define THRESHOLD 2
	#define TIMEOUT 100
	
	int jumpCount;
	int penalty;
	
	my_predictor(void) : gshare_history(0){
		//constructor - we start with the first meta predictor active
		firstMeta = true;
		//First choice
		tournament_choice = 0;
		memset(gshare_counters, 0, sizeof(gshare_counters));
		
		penalty = 0;
		jumpCount=0;
	}
	
	branch_update *predict (branch_info & b){
		bi = b;
		
		//Only 
		if(b.br_flags & BR_CONDITIONAL){
			u.address = b.address;
			
			
			//PART A - make predictions
			//Bimodal
			bimodal_index = u.address & (( 1 << (BIMODAL_INDEX_BITS)) -1);
			
			if(bimodal_counters[bimodal_index] >=2){
				u.bimodal_prediction = true;
			}else{
				u.bimodal_prediction = false;
			}
			
			//gShare
			u.gshare_index = (gshare_history  << ( GSHARE_TABLE_BITS - GSHARE_HISTORY_LENGTH)) ^ (b.address & ((1 << GSHARE_TABLE_BITS) -1 ));
			u.gshare_prediction = (gshare_counters[u.gshare_index] >> 1);
			
			//two level branch predictor
			two_level_index = u.address & ((1<< (TWO_LEVEL_INDEX_BITS)) -1);
			gIndex = two_level_history | (two_level_index << TWO_LEVEL_HISTORY_LENGTH);
										  
			if(firstMeta){	
				//printf("FIRST\n");
				//We are using the first meta predictor - we apply tournament strategy to detect which predictor can actually do prediction.
				if(tournament_choice < 2){
					u.final_prediction = u.gshare_prediction;
					u.direction_prediction(u.gshare_prediction);
				}else{
					u.final_prediction = u.bimodal_prediction;
					u.direction_prediction(u.bimodal_prediction);
				}
				//Use second predictor
			}else{
				//printf("SECOND\n");
				if(two_level_counters[gIndex] >= 2){
					u.direction_prediction(true);
				}else{
					u.direction_prediction(false);
				}
				if(jumpCount < TIMEOUT){
					jumpCount++;
				}else{
					jumpCount = 0;
					penalty = 0;
					firstMeta = true;
				}
			}
			//No conditional branch
		}else{
			u.target_prediction(true);
		}
		
		u.target_prediction(0);
		return &u; 
	}
	
	void update (branch_update *u , bool taken, unsigned int target){
		//This method should make our first meta predictor smarter, using the 
		//tournament strategy. Also, this method should evaluate the overall performance
		//of the first meta predictor. In case performance drops, firstMeta should be flipped.
		
		
		if(bi.br_flags & BR_CONDITIONAL){
			unsigned char *gshare_counter = &gshare_counters[((my_update*)u)->gshare_index];
			bimodal_index = ((my_update*)u)->address & (1 << (BIMODAL_INDEX_BITS)) -1;
			
			//Get index for address part 
			two_level_index = ((my_update*)u)->address & ((1<< (TWO_LEVEL_INDEX_BITS)) -1);
			gIndex = two_level_history | (two_level_index << TWO_LEVEL_HISTORY_LENGTH);

			if(taken){
				//gShare
				if(*gshare_counter < 3){
					(*gshare_counter)++;
				}
				
				//bimodal
				if(bimodal_counters[bimodal_index] < 3){
					bimodal_counters[bimodal_index]++;
				}
				
				//two_level
				if(two_level_counters[gIndex] < 3){
					two_level_counters[gIndex]++;
				}
				
			}else{
				//gShare
				if(*gshare_counter > 0){
					(*gshare_counter)--;
				}
				
				//bimodal
				if(bimodal_counters[bimodal_index] > 0){
					bimodal_counters[bimodal_index]--;
				}
				
				//two_level
				if(two_level_counters[gIndex] > 0){
					two_level_counters[gIndex]--;
				}
			}
			
			//Update gShare history
			gshare_history <<=1;
			gshare_history |= taken;
			gshare_history &= (1 << GSHARE_HISTORY_LENGTH)-1;
			
			//Update two_level history
			two_level_history <<= 1;
			two_level_history |= taken;
			two_level_history &= (1 << TWO_LEVEL_HISTORY_LENGTH) -1;
			
			
			//Update tournament scoring
			if(taken){
				if(((my_update*)u)->gshare_prediction && !(((my_update*)u)->bimodal_prediction)){
					if(tournament_choice > 0){	
						tournament_choice--;
					}
				}
				
				if(!(((my_update*)u)->gshare_prediction) && (((my_update*)u)->bimodal_prediction)){
					if(tournament_choice < 3){	
						tournament_choice++;
					}
				}
			}else{
				if(((my_update*)u)->gshare_prediction && !(((my_update*)u)->bimodal_prediction)){
					if(tournament_choice < 3){	
						tournament_choice++;
					}
				}
				
				if(!(((my_update*)u)->gshare_prediction) && (((my_update*)u)->bimodal_prediction)){
					if(tournament_choice > 0){	
						tournament_choice--;
					}
				}
			}
			
			
			//Update first metapredictor performance measurement
			if(penalty > THRESHOLD){
				penalty = 0;
				firstMeta = false;
			}
			
			if(taken && (((my_update*)u)->final_prediction)){
				//Correctly predicted as taken
				if(penalty > 0)
					penalty--;
			}else if(!taken && !(((my_update*)u)->final_prediction)){
				//Correctly predicted as not taken
				if(penalty > 0)
					penalty--;
			}else{
				//Wrong prediction, penalty the predictor
				penalty++;
			}
			
			//printf("PENALTY: %d\n", penalty);
			
		}
	}
};
